Stack Data Structure
Codes:
- Method 1 using List
- Method 2 using deque
This track of the course covers the topic "Stack".
In details, this track will cover:
Objective: The objective of this track is to familiarize the learners with Stack.
Track Content:
Assessment: All Tracks in every week are associated with weekly contests.
This video discusses the various applications of Stack.
This video discusses the implementation of Stack in C++.
Code:
In this video we'll talk about stack in java collections
Code:
This video discusses the below problem:
Given a string of parenthesis ({, }, (, ), [ and ]), we need to check if this string is balanced or not.
Code:
This video discusses the problem of implementation of Two stacks in a single array.
Codes:
This video discusses the problem of implementation of K Stacks in an array
Codes:
This video discusses the problem of Stock span problem along with few variations.
Codes:
This video discusses the below problem:
Given an array of distinct integers, find the closest (positive wise) greater on left of every element. If there is no greater element on l;eft, then print -1
Codes:
This video discusses the below problem:
Given an array of distinct integers, find the NextGreater(position-wise closest and on the right side) of every array elements.
Codes:
This video discusses the first part of the problem of calculating the Largest Rectangular Area in a Histogram.
Codes:
This video discusses the second part of the problem of calculating the Largest Rectangular Area in a Histogram.
Codes:
Design a stack that supports normal stack operatiosn in O(1) and also supprots getMin() in O(1)
Codes:
Infix, prefix and Postfix are three different ways to write mathematical expressions. This video introduces these three and talks about their advantages/distadvantages.
This video talks about simple method for Infix to Postfix conversion.
This video talks about infix to postfix conversion using stack.
This video talks about a simple, efficient and stack based solution for evaluation of postfix.
This video talks about simple method for Infix to Prefix Conversion.
This video talks about stack based efficient solution for Infix to Prefx conversion.
This method talks about simple, efficient and stack based solution for evaluation of prefix.

How to understand a stack practically?
There are many real-life examples of a stack. Consider the simple example of plates stacked over one another in a canteen. The plate that is at the top is the first one to be removed, i.e. the plate that has been placed at the bottommost position remains in the stack for the longest period of time. So, it can be simply seen to follow LIFO/FILO order.Implementing Stack using Arrays
10 pushed into stack
20 pushed into stack
30 pushed into stack
30 popped from stack
Implementing Stack using Linked List
10 pushed to stack
20 pushed to stack
30 pushed to stack
30 popped from stack
Top element is 20
Pros: The linked list implementation of stack can either grow or shrink according to the needs at runtime.
Cons: Requires extra memory due to involvement of pointers.
stack< data_type > stack_name;
Here,
data_type: This defines the type of data to be
stored in the stack.
stack_name: This specifies the name of the stack.
The stack is : 1 5 20 30 10
s.size() : 5
s.top() : 1
s.pop() : 5 20 30 10

Pop :
4
3
2
1
0
Element on stack top : 4
Element is found at position 3
Element not found
a op1 b op2 c op3 dThe compiler first scans the expression to evaluate the expression b * c, then again scan the expression to add a to it. The result is then added to d after another scan.
If op1 = +, op2 = *, op3 = +
abcd^e-fgh*+^*+i-
postfix evaluation: -4
757
Popped element from stack1 is 11
Popped element from stack2 is 40
[1 2 3 4 5]Solution - We will traverse the linked list and push all the nodes of the linked list to the stack. Since stack have property of Last In, First Out, List is automatically reversed when we will pop the stack elements one by one.
[5 4 3 2 1]
void printreverse(Node *head)Time Complexity : O(n)
{
stack < Node* > s
current = head
while(current != NULL)
{
s.push(current)
current = current->next
}
while( ! s.empty())
{
node = s.top()
print(node->data)
s.pop()
}
}
Input : [ ( ) ] { } { [ ( ) ( ) ] ( ) }
Output : true
Input : [ ( ] )
Output : false
Solution : Follow the streps below -// function to check if paranthesis are balancedTime Complexity : O(n)
bool areParanthesisBalanced(string expr)
{
stack < char > s
for i=0 to expr.size() {
if (expr[i]=='('||expr[i]=='['||expr[i]=='{') {
s.push(expr[i])
continue
}
// stack can not be empty for closing bracket
if s.empty()
return false
switch (expr[i]) {
case ')': {
x = s.top()
s.pop()
if (x=='{' || x=='[')
return false
break
}
case '}': {
x = s.top();
s.pop();
if (x=='(' || x=='[')
return false
break
}
case ']': {
x = s.top();
s.pop();
if (x =='(' || x == '{')
return false
break
}
}
}
// Check Empty Stack
return (s.empty())
}
Input : [13, 7, 6, 12]Solution : Follow the below steps -
Output
Element NGE
13 --> -1
7 --> 12
6 --> 12
12 --> -1
// Next greater ElementTime Complexity : O(n)
void printNGE(arr, n)
{
stack < int > s
s.push(arr[0])
for i=0 to n-1 {
if (s.empty()) {
s.push(arr[i])
continue
}
while (s.empty() == false && s.top() < arr[i]) {
print(s.top() + "-->" + arr[i])
s.pop()
}
s.push(arr[i])
while (s.empty() == false) {
print(s.top() + "-->" + -1)
s.pop()
}
}
}
A | O(n logk) |
B | O(nk) |
C | O(n<sup>2</sup>) |
D | O(k<sup>2</sup>) |